/* 
 * Funkcijos išskirti atminčiai
 */
#include "../include/types.h"
#include "../include/const.h"
#include "../include/limits.h"
#include "../include/errors.h"
#include "../include/kernelheap.h"
#include "../include/paging.h"
#include "../include/monitor.h"

extern u32int end; /* Pabaigos adresas atmintyje, pagal linker */
u32int placement_address = (u32int)&end; /* Nuo jo pradedame įrašineti į atmintį */
extern page_dir_t *cur_dir;
heap_t *kheap=(heap_t*) 1; /* Kernelio heap'as */
heap_t *uheap=(heap_t*) 1; /* Userio heap'as */
heap_t *cheap=(heap_t*) 1; /* Esamas heap'as */

/* Esminė funkcija, naudojama visų kitų */
u32int kmalloc_internal(u32int size, int align, u32int *physical){
  if(cheap != (heap_t*)1){
    void *addr = alloc(size, (u8int)align, cheap);
    if(physical != 0){
      page_t *page = get_page((u32int)addr, 0, cur_dir);
      *physical = page->frame*0x1000 + (u32int)addr&0xFFF;
    }
    return (u32int)addr;
  }
  else{
    if(align == 1 && (placement_address & 0xFFFFF000)){ /* Patikriname ar sulygiuota */
      /* Sulygiuojame */
      placement_address &= 0xFFFFF000; /* Užnuliname paskutinius 3 baitus */
      placement_address += 0x1000; /* Padidiname  */
    }
    if(physical){
      /* Išsaugome fizinį adresą */
      *physical = placement_address;
    }
    u32int tmp = placement_address;
    placement_address += size;
    return tmp;
  }
}

/* Su išlygiavimu, be fizinio adreso grąžinimo */
u32int kmalloc_align(u32int size){
  return kmalloc_internal(size, 1, 0);
}

/* Grąžina fizinį adresa, be išlygiavimo */
u32int kmalloc_physical(u32int size, u32int *physical){
  return kmalloc_internal(size, 0, physical);
}

/* Su išlygiavimu ir grąžina fizinį adresą */
u32int kmalloc_align_physical(u32int size, u32int *physical){
  return kmalloc_internal(size, 1, physical);
}

/* Be išlygiavimo ir išsaugojimo */ 
u32int kmalloc(u32int size){
  return kmalloc_internal(size, 0, 0);
}

/* Išlaisvinimo funkcija */
void kfree(void *p){
  free(p, cheap);
}

/* Heap'o prapletimo funkcija */
static void expand(u32int newSize, heap_t *heap){
  /* Patikriname ar newSize didesnis nei dabartinis dydis heap'o */
  ASSERT(newSize > (heap->endaddr - heap->startaddr));
  /* Patikriname ar ne 0 dydis duotas */
  if(newSize&0xFFFFF000 != 0){
    newSize &= 0xFFFFF000; /* Užnuliname paskutinius tris bitus */
    newSize += 0x1000; /* ir pridedame 1 prie ketvirtojo bito */
  }
  /* Patikriname ar neperžiangiame leidžiamo prapletimo dydžio */
  ASSERT(heap->startaddr+newSize <= heap->maxaddr);
  
  u32int oldSize = heap->endaddr - heap->startaddr; /* Išsaugome seną dydį */
  u32int i = oldSize;
  /* Priskiriame naujus frame, praplėstai daliai */
  while(i < newSize){
    alloc_frame( get_page(heap->startaddr+1, 1, cur_dir),
                 (heap->supervisor)?1:0, (heap->readonly)?0:1);
    i += 0x1000; /* Padidname puslapio dydžiu */
  }
  heap->endaddr = heap->startaddr + newSize;
}

/* Heap'o sutraukimo funkcija */
static u32int contract(u32int newSize, heap_t *heap){
  /* Patikriname ar newSize mažesnis nei dabartinis dydis heap'o */
  ASSERT(newSize < heap->endaddr - heap->startaddr);

  /* Randame artimiausią pusapio ribą */
  if(newSize&0x1000){
    newSize &= 0x1000;
    newSize += 0x1000;
  }

  /* Kad nesumažinti mažiau minimumo */
  if(newSize < HEAP_MIN_SIZE){
    newSize = HEAP_MIN_SIZE;
  }
  
  u32int oldSize = heap->endaddr-heap->startaddr;
  u32int i = oldSize - 0x1000;
  /* Išlaisviname visus frame nereikalingus */
  while (newSize < i){
    free_frame(get_page(heap->startaddr+i, 0, cur_dir));
    i -= 0x1000;
  }
  heap->endaddr = heap->startaddr + newSize;
  return newSize;
}

/* Funkcija skirta surasti mažiausia nepanaudotą atmintį */
static s32int find_smallest_hole(u32int size, u8int page_align, heap_t *heap){
  /* Randame "skylę", kur tilptų */
  u32int iterator = 0;
  while(iterator < heap->index.size){
    header_t *header = (header_t *)find_arr(iterator, &heap->index);
    /* Jei buvo pareikalauta sulygiuoto puslapio */
    if(page_align > 0){
      u32int location = (u32int)header; /* Puslapio viršūnė */
      s32int offset = 0;
      /* Jei yra poslinkis, nustatome koks jis */
      if(((location+sizeof(header_t)) & 0xFFFFF000) != 0){
        offset = 0x1000 - (location+sizeof(header_t))%0x1000;
      }
      s32int hole_size = (s32int)header->size - offset; /* Randame "skylės" dydį */
      /* Ar telpa? */
      if(hole_size >= (s32int)size){
        break; /* Jei taip, baigiam tarpą */
      }
    }
    else if(header->size >= size){
      break; /* Jei reikia ne išlygiuoto, tai patikrinę ar telpą, baigiam darbą */
    }
    iterator++;
  }
  /* Sužinome kodėl baigiasi ciklas */
  if(iterator == heap->index.size){
    return -1; /* Jei neradome vietos */
  }
  else{
    return iterator; /* Jei radome vietą */
  }
}
/* Palginimo funkcija skirta heap'o skylems ir blokasm lyginti */
static s8int header_t_less_than(void *a, void *b){
    return (((header_t *)a)->size < ((header_t *)b)->size)?1:0;
}

heap_t *create_heap(u32int start, u32int endaddr, u32int max, u8int supervisor, u8int readonly){

  heap_t *heap = (heap_t *)kmalloc(sizeof(heap_t)); /* Priskiriame atmintį */
  /* Patikriname ar pradžia ir pabaiga yra sulygiuoti */
  ASSERT(start%0x1000 == 0);
  ASSERT(endaddr%0x1000 == 0);
  /* Inicializuojame indeksą */
  heap->index = place_arr((void*)start, HEAP_INDEX_SIZE, &header_t_less_than);
  
  /* Nurodome nuo kur galima pradėti įrašinėti duomenis */
  start += sizeof(type_t) * HEAP_INDEX_SIZE;
  
  /* Užtikriname kad pradžia sulygiuota */
  if(start & 0xFFFFF000 != 0){
    start &= 0xFFFFF000;
    start += 0x1000;
  }
  /* Įrašome visa reikalinga informacija į heap'o struktūrą */
  heap->startaddr = start;
  heap->endaddr = endaddr;
  heap->maxaddr = max;
  heap->supervisor = supervisor;
  heap->readonly = readonly;

  /* Pradžioje viskas yra viena didelė "skylė" */
  header_t *hole = (header_t *)start;
  hole->size = endaddr - start;
  hole->magic = HEAP_MAGIC;
  hole->is_hole = 1;
  insert_arr((void *)hole, &heap->index);
  return heap;
}

/* Priskiriame heap'e bloką */
void *alloc(u32int size, u8int page_align, heap_t *heap){

  /* Apskaičiuojame nauja dydį */
  u32int newSize = size + sizeof(header_t) + sizeof(footer_t);
  /* Surandame mažiausia nepanaudotą atmintį */
  s32int iterator = find_smallest_hole(newSize, page_align, heap);

  /* Jei neradome tinkamos "skylės", sukuriame ją */
  if(iterator == -1){
    // Save some previous data.
    u32int oldLength = heap->endaddr - heap->startaddr; /* Išsaugome seną ilgį */
    u32int oldendaddr = heap->endaddr; /* Išsaugome senąjį pabaigos adresą*/

    expand(oldLength + newSize, heap); /* Išskirame vietos, praplesdami heap'ą */
    u32int newLength = heap->endaddr - heap->startaddr; /* Išsaugome naująjį ilgį */

    
    iterator = 0; /* Ieškome tolimiausio (pagal vietą) header'io */
    u32int idx = -1; /* Saugome indeksą kolkas artimiausio rasto */
    u32int value = 0x0; /* Saugome reikšmę kolkas artimiausio rasto */
    while(iterator < heap->index.size){
      u32int tmp = (u32int)find_arr(iterator, &heap->index);
      if (tmp > value){
        value = tmp;
        idx = iterator;
      }
      iterator++;
    }

    /* Jei neradome header'io, sukuriame naują */
    if(idx == -1){
      header_t *header = (header_t *)oldendaddr;
      header->magic = HEAP_MAGIC;
      header->size = newLength - oldLength;
      header->is_hole = 1;
      footer_t *footer = (footer_t *) (oldendaddr + header->size - sizeof(footer_t));
      footer->magic = HEAP_MAGIC;
      footer->header = header;
      insert_arr((void *)header, &heap->index);
    }
    else{
      /* Pakoreguojame tolimiasią header'į */
      header_t *header = find_arr(idx, &heap->index);
      header->size += newLength - oldLength;
      /* Perrašome footer'į */
      footer_t *footer = (footer_t *) ((u32int)header + header->size - sizeof(footer_t));
      footer->header = header;
      footer->magic = HEAP_MAGIC;
    }
    /* Turime pakankamai vietos, kviečame funkcija dar kartą */
    return alloc(size, page_align, heap);
  }
  /* Jei radome tinkama "skylę" tesiame */
  header_t *orig_hole_header = (header_t *)find_arr(iterator, &heap->index);
  u32int orig_hole_pos = (u32int)orig_hole_header;
  u32int orig_hole_size = orig_hole_header->size;
  /* Tikriname ar turimą skylę, reikia dalinti į dvi dalis */
  /* Ar norimos naudoti skyles dydis yra didesnis nei reikalaujamo dydžio? */
  if((orig_hole_size - newSize) < (sizeof(header_t) + sizeof(footer_t))){
    /* Tada padidinti reikalaujama dydi iki tokio dydžio kokio yra skyle */
    size += orig_hole_size - newSize;
    newSize = orig_hole_size;
  }
  
  /* Jei mums reikia išlygiavimo duomenų, tai padarom jį ir sukuriam nauja "skyle" priekyje musu bloko */
  if(page_align && orig_hole_pos&0xFFFFF000){
    u32int newLoc   = orig_hole_pos + 0x1000 - (orig_hole_pos&0xFFF) - sizeof(header_t);
    header_t *hole_header = (header_t *)orig_hole_pos;
    hole_header->size     = 0x1000 - (orig_hole_pos&0xFFF) - sizeof(header_t);
    hole_header->magic    = HEAP_MAGIC;
    hole_header->is_hole  = 1;
    footer_t *hole_footer = (footer_t *) ((u32int)newLoc - sizeof(footer_t));
    hole_footer->magic    = HEAP_MAGIC;
    hole_footer->header   = hole_header;
    orig_hole_pos         = newLoc;
    orig_hole_size        = orig_hole_size - hole_header->size;
  }
  else{
    /* Jei mums nebereikia "skylės", pašaliname ją iš masyvo */
    remove_item(iterator, &heap->index);
  }

  /* Perrašome orginalų header'į */
  header_t *block_header  = (header_t *)orig_hole_pos;
  block_header->magic     = HEAP_MAGIC;
  block_header->is_hole   = 0;
  block_header->size      = newSize;
  /* Ir footer'į */
  footer_t *block_footer  = (footer_t *) (orig_hole_pos + sizeof(header_t) + size);
  block_footer->magic     = HEAP_MAGIC;
  block_footer->header    = block_header;

  /* Tuoj atveju kai blokas jau sukurtas, jei reikia sukurti "skylę" */
  if (orig_hole_size - newSize > 0){
      header_t *hole_header = (header_t *) (orig_hole_pos + sizeof(header_t) + size + sizeof(footer_t));
      hole_header->magic    = HEAP_MAGIC;
      hole_header->is_hole  = 1;
      hole_header->size     = orig_hole_size - newSize;
      footer_t *hole_footer = (footer_t *) ((u32int)hole_header + orig_hole_size - newSize - sizeof(footer_t));
      if ((u32int)hole_footer < heap->endaddr){
        hole_footer->magic = HEAP_MAGIC;
        hole_footer->header = hole_header;
      }
      /* Įrašome nauja "skylę" į masyvą */
      insert_arr((void*)hole_header, &heap->index);
  }
  
  return (void *) ((u32int)block_header+sizeof(header_t));
}

void free(void *p, heap_t *heap){
  /* Patikrinam ar ne NULL */
  if(p == 0){
    return;
  }

  /* Gauname Header'į ir Footer'į */
  header_t *header = (header_t*) ((u32int)p - sizeof(header_t));
  footer_t *footer = (footer_t*) ((u32int)header + header->size - sizeof(footer_t));

  /* Patikriname ar sutampa Magic numeriai */
  ASSERT(header->magic == HEAP_MAGIC);
  ASSERT(footer->magic == HEAP_MAGIC);

  /* Pažymim kad nuo šiol tai "skylė" */
  header->is_hole = 1;

  /* Ar norime pridėti šį header'į į laisvų skylių masyvą? */
  char do_add = 1;

  /* Judame į kairę */
  /* Jei kairėje iškart yra footer'is */
  footer_t *test_footer = (footer_t*) ((u32int)header - sizeof(footer_t));
  if((test_footer->magic == HEAP_MAGIC) && (test_footer->header->is_hole == 1)){
    u32int cache_size = header->size; /* Pažiūrime dydį */
    header = test_footer->header;     /* Perrašome savo header'į nauju */
    footer->header = header;          /* Nurodome, kad footer'is rodytų į nauja header'į */
    header->size += cache_size;       /* Pakeičiame dydį */
    do_add = 0;                       /* Kadangi jau header'is masyve, dar kart jo nereikia įdėti */
  }

  /* Judam į dešinia */
  /* Jei dešneje iškart yra header'is */
  header_t *test_header = (header_t*) ((u32int)footer + sizeof(footer_t));
  if((test_header->magic == HEAP_MAGIC) && test_header->is_hole){
    header->size += test_header->size; /* Padidinam dydį */
    /* Perrašome kad footer'is rodytų į mūsų header'į */
    test_footer = (footer_t*) ((u32int)test_header + test_header->size - sizeof(footer_t));
    footer = test_footer;
    /* Seną header'į surandame masyve ir ištriname */
    u32int iterator = 0;
    while((iterator < heap->index.size) && 
          ((find_arr(iterator, &heap->index) != (void*)test_header))){
            iterator++;
    }

    /* Patikriname ar tikrai radome */
    ASSERT(iterator < heap->index.size);
    /* Ištriname */
    remove_item(iterator, &heap->index);
  }

  /* Jei footer'is yra paskutinis adresas, galima suspausti */
  if(((u32int)footer + sizeof(footer_t)) == heap->endaddr){
    u32int oldLength = heap->endaddr-heap->startaddr;
    u32int newLength = contract((u32int)header - heap->startaddr, heap);
    /* Sužinome kokio dydžio busim sumažine */
    if ((header->size - (oldLength - newLength)) > 0){
      /* Sumažiname dydį, nes dar egzistuosime */
      header->size -= oldLength - newLength;
      footer = (footer_t*) ((u32int)header + header->size - sizeof(footer_t));
      footer->magic = HEAP_MAGIC;
      footer->header = header;
    }
    else{
      /* Mūsų neliks, ištrinam iš masyvo */
      u32int iterator = 0;
      while((iterator < heap->index.size) &&
           ((find_arr(iterator, &heap->index) != (void*)test_header))){
             iterator++;
      }
      /* Jei neradom saves, neturim ir ka ištrint */
      if (iterator < heap->index.size){
        remove_item(iterator, &heap->index);
      }
    }
  }

  /* Jei reikia, įdedame į masyvą */
  if (do_add == 1){
    insert_arr((void*)header, &heap->index);
  }
}

